package com.gitee.wsl.ext.array.sort

import com.gitee.wsl.ext.array.swap

/**
 * Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares
 * each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated
 * until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort,
 * is named for the way smaller or larger elements "bubble" to the top of the list. Although the algorithm is simple,
 * it is too slow and impractical for most problems even when compared to insertion sort. It can be practical
 * if the input is usually in sorted order but may occasionally have some out-of-order elements nearly in position.
 *
 * Worst-case performance:       O(n^2)
 * Best-case performance:        O(n)
 * Average performance:          O(n^2)
 * Worst-case space complexity:  O(1)
 */
fun<T : Comparable<T>> Array<T>.bubbleSort(){
    var exchanged: Boolean

    do {
        exchanged = false
        for (i in 1 until this.size) {
            if (this[i] < this[i - 1]) {
                this.swap(i, i - 1)
                exchanged = true
            }
        }
    } while (exchanged)
}